package com.gy.algorithm.carl.linklistexa;

/**
 * @BelongsProject: javabase
 * @BelongsPackage: com.gy.algorithm.carl.linklistexa
 * @Author: gy
 * @Date: 2024/10/26 14:38
 * @Description:
 */
public class Test {


    public static void sortColors(int[] nums) {
        mergeSort(nums,0,nums.length - 1);
    }

    public static void mergeSort(int[] nums,int start ,int end){
        if(start < end){
            int mid = (start + end) >> 1;
            mergeSort(nums,start,mid);
            mergeSort(nums,mid + 1,end);
            merge(nums,start,end,mid);
        }
    }

    public static void merge(int[] nums,int start ,int end,int mid){
        int[] temps = new int[end + 1];

        int left = start;
        int right = mid + 1;
        int index = start;

        while(left <= mid && right <= end){
            if(nums[left] < nums[right]){
                temps[index++] = nums[left++];
            }else{
                temps[index++] = nums[right++];
            }
        }
        while(left <= mid)  temps[index++] = nums[left++];
        while(right <= end)  temps[index++] = nums[right++];

        for (int i = start; i <= end; i++) {
            nums[i] = temps[i];
        }
    }
}
